import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deque<Item> implements Iterable<Item> {

    private int size;
    private Node<Item> first;
    private Node<Item> last;

    // construct an empty deque
    public Deque() {
    }

    private static class Node<Item> {
        final Item item;
        Node<Item> next;
        Node<Item> previous;

        public Node(Item item) {
            this.item = item;
        }
    }

    // is the deque empty?
    public boolean isEmpty() {
        return size == 0;
    }

    // return the number of items on the deque
    public int size() {
        return size;
    }

    // insert the item at the front
    public void addFirst(Item item) {
        if (item == null)
            throw new NullPointerException("Null values are not allowed in Deque collection");

        if (first == null) {
            last = first = new Node<Item>(item);
        }
        else {
            Node<Item> newNode = new Node<Item>(item);
            first.previous = newNode;
            newNode.next = first;
            first = newNode;
        }
        size++;
    }

    // insert the item at the front
    public void addLast(Item item) {
        if (item == null)
            throw new NullPointerException("Null values are not allowed in Deque collection");

        if (last == null) {
            last = first = new Node<Item>(item);
        }
        else {
            Node<Item> newNode = new Node<Item>(item);
            last.next = newNode;
            newNode.previous = last;
            last = newNode;
        }
        size++;
    }

    // delete and return the item at the front
    public Item removeFirst() {
        if (first == null)
            throw new NoSuchElementException("Empty list. No elements to remove.");

        Item result = first.item;
        if (size == 1) {
            first = last = null;
        }
        else {
            first = first.next;
        }
        size--;
        return result;
    }

    // delete and return the item at the end
    public Item removeLast() {
        if (last == null)
            throw new NoSuchElementException("Empty list. No elements to remove.");

        Item result = last.item;
        if (size == 1) {
            first = last = null;
        }
        else {
            last = last.previous;
            last.next = null;
        }
        size--;
        return result;
    }

    // return an iterator over items in order from front to end
    public Iterator<Item> iterator() {
        return new DequeIterator();
    }

    private class DequeIterator implements Iterator<Item> {
        Node<Item> position;

        DequeIterator() {
            position = first;
        }

        @Override
        public boolean hasNext() {
            return position != null;
        }

        @Override
        public Item next() {
            if (position == null)
                throw new NoSuchElementException();

            Node<Item> current = position;
            position = current.next;
            return current.item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}